//华为od机考真题-最少面试官数
//公司正在组织集中面试，每场面试需要一个面试官，现在以数组的形式给出了
//每场面试的开始时间和结束时间的时间安排表 [si, ei] (si < ei)），
//为避免面试冲突，请问至少需要多少位面试官，才能满足这些面试安排。
//示例 1:
//输入: [[0, 30],[5, 10],[15, 20]]输出: 2
//示例 2:
//输入: [[7,10],[2,4]]输出: 1
//这是一道时间规划问题
//思路：先排序，然后比较endTime 和 startTime

//n为每个需要面试的总场次，m每个面试官最大面试场次，
//后面给出每场面试的开始和结束时间，面试官在一段时间内只能面试一个人
//输入：n  总场次如 5
//m 每人人最大面试场次如 2
//n组  如{
//[1,2],[2,5],[4, 30],[5, 10],[15, 20]
//}
//输出：最少面试官人数  如 3

//                     2         3
//  1234567890123456789012345678901234567890
//  -
//   ---
//     ------------------------------------
//      -----
//                -----

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x) freopen("d:/oj/" #x ".in", "r", stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

struct TimeSec {
    int timeS = 0;
    int timeE = 0;
};

struct Interviewer {
    int index = 0;   // for test
    int freeCount = 0;
    int start = 0;
    int end = 0;
    bool operator> (Interviewer other) const {
        return end > other.end;
    }
};

// nMaxCount 每个面试官最多面试次数
int getMaxInterviewer(const vector<TimeSec>& vtTimeSection, int nMaxCount) {
    std::sort(vtTimeSection.begin(), vtTimeSection.end(), [](TimeSec t1, TimeSec t2){return t1.timeS < t2.timeS;});
    int nViewerCnt = 0;
    priority_queue<Interviewer, vector<Interviewer>, greater<Interviewer> > quViewer;
    for (size_t i = 0; i < vtTimeSection.size(); i++) {
        auto [curSt, curEd]  = vtTimeSection[i];
        if (quViewer.empty()) {
            quViewer.push({nViewerCnt, nMaxCount, 0, 0});
            nViewerCnt++;
        }
        //      ------   curTime
        // ----          viewer's free time
        auto viewer = quViewer.top();  // quViewer.pop();
        if (viewer.end > curSt) {
            // add viewer
            viewer = {nViewerCnt, nMaxCount, 0, 0};
            nViewerCnt++;
        } else {
            quViewer.pop();
        }
        viewer.freeCount--;
        viewer.start = curSt;
        viewer.end = curEd;
        if (viewer.freeCount > 0) {
            quViewer.push(viewer);
        }
    }
    return nViewerCnt;
}

int main_my_viewer() {
    int m = 0;
    int n = 0;
    vector<TimeSec> vt1 ;
    printf("use interviewer = %d\n", getMaxInterviewer({{1, 3},{5,6},{12,35},{3,65},{22, 43},{25, 91},{2, 5},{4,9},{23, 90},{12,44},{31, 66},{14, 70},{64, 80},{53,83},{36,80},{12, 44},{28,64},{15, 29},}, 3));
    printf("use interviewer = %d\n", getMaxInterviewer({{1, 3},{5,6},{12,35},{3,65},{22, 43},{25, 91},{2, 5},{4,9},{23, 90},{12,44},{31, 66},{14, 70},{64, 80},{53,83},{36,80},{12, 44},{28,64},{15, 29},}, 3));
    printf("use interviewer = %d\n", getMaxInterviewer({{1, 3},{5,6},{12,35},{3,65},{22, 43},{25, 91},{2, 5},{4,9},{23, 90},{12,44},{31, 66},{14, 70},{64, 80},{53,83},{36,80},{12, 44},{28,64},{15, 29},}, 3));
// {0, 30},{5, 10},{15, 20} 输出: 2
    return 0;
}


//输入: [[0, 30],[5, 10],[15, 20]]输出: 2
//输入: [[7,10],[2,4]]输出: 1
